/**
 * 这个写法会超时
 */
function searchInsert(nums: number[], target: number): number {
  const length = nums.length
  let half = Math.floor(length / 2)
  if (half === 0) {
    if (nums[half] >= target) {
      return 0
    } else {
      return 1
    }
  }
  while (true) {
    if (nums[half] === target) {
      return half
    }
    if (nums[half] < target) {
      half = Math.floor((half + 1 + length) / 2)
      if (half >= length) return length
    } else if (nums[half] > target) {
      half = Math.floor(half / 2)
      if (half === 0) {
        if (nums[half] >= target) {
          return 0
        } else {
          return 1
        }
      }
    }
  }
};

/**
 * 力扣官方二分法
 */
function searchInsert2(nums: number[], target: number): number {
  const n = nums.length
  let left = 0, right = n - 1, ans = n
  while (left <= right) {
    let half = (right + left) >> 1
    if (target <= nums[half]) { // 这里考虑重复元素的情况
      ans = half
      right = half - 1
    } else {
      left = half + 1
    }
  }
  return ans
}
module.exports.searchInsert = searchInsert2